Презентация «Информационные модели на графах»

Информационные модели на графах Учитель информатики МБОУ «Гимназия №1» г.Ядрин Порфирьева Н.Н.

Информационная модель - набор свойств, содержащий всю необходимую информацию об исследуемом объекте. Информационная модель - набор свойств, содержащий всю необходимую информацию об исследуемом объекте. Виды моделей Образные Рисунки Фотографии Смешанные Таблицы Схемы Графики Диаграммы Знаковые Словесные описания Формулы

Схема - это представление объекта в общих, главных чертах с помощью условных обозначений. Какие виды схем вы знаете? Карта с.Б.Сундырь Моргаушского района

Граф состоит из вершин, связанных линиями. Граф состоит из вершин, связанных линиями. Направленная линия (со стрелкой) называется дугой. Линия ненаправленная (без стрелки) называется ребром. Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей. А В С петля ребро дуга Граф – это схема являющаяся наглядным представлением состава и структуры системы.

Тема урока: Информационные модели на графах Цели урока: расширить представления учащихся о видах информационных моделей; сформировать представление о графах как наглядном средстве представления структуры и состава системы;

Неориентированный граф - Неориентированный граф - граф, вершины которого соединены ребрами. С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений. 1 2 5 4 3 6 Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза. Цикл – цепь, начальная и конечная вершины которой совпадают. Граф с циклом называют сетью.

Ориентированный граф - граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений. 6 5 4 3 2 1

с. Аликово г. Ядрин с. Моргауши 53 км 40 км 46 км Взвешенный граф - граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).

Задача от Смешарика. Пройди по схеме и прочитай как называется граф, который одновременно содержит ребра и дуги. Задача от Смешарика. Пройди по схеме и прочитай как называется граф, который одновременно содержит ребра и дуги. 5 2 1 4 3 С М Ш Й Ы Е А Н Н Пример смешанного графа

Бараш решил сходить в гости к Пину. Сколько существует различных путей?

Задачи на поиск путей в Графе Задача 1 На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M? B A K C E G F H L M Ответ: 12

Задача 2 На ри­сун­ке – схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, З, И. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город И? A И Б Д В Ж З Е Г Ответ: 16

Задача 3 Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и F.   A B C D E F A   5         B 5   9 7 8   C   9     4   D   7     3   E   8 4 3   7 F         7   8 А В D F C E 5 9 7 3 4 7 Ответ: 20